/**
 * 
 */
package string.passed2;

import java.util.Arrays;
import java.util.List;

/**
 * @author xyyi
 *
 */
public class RegularExpression {

    /**
     Implement regular expression matching with support for '.' and '*'.

    '.' Matches any single character.
    '*' Matches zero or more of the preceding element.
    
    The matching should cover the entire input string (not partial).
    
    The function prototype should be:
    bool isMatch(const char *s, const char *p)
    
    Some examples:
    isMatch("aa","a") ? false
    isMatch("aa","aa") ? true
    isMatch("aaa","aa") ? false
    isMatch("aa", "a*") ? true
    isMatch("aa", ".*") ? true
    isMatch("ab", ".*") ? true
    isMatch("aab", "c*a*b") ? true
    
    isMatch("a", "b*a") ? true
     */
    public boolean isMatch(String s, String p) {
        // Start typing your Java solution below
        // DO NOT write main() function
//        return isMatchR(s, p, 0, 0);
        return isMatchRWithPlus(s, p, 0, 0);
    }

    public static void abc() {
        int a;
        int b = a = 1;
    }

    private boolean isMatch(String s, String p, int si, int pi) {

        if (p.length() == pi)
            return s.length() == si;

        if (s.length() == si) {
            if (pi < p.length() - 1 && p.charAt(pi + 1) == '*') {
                while (++pi < p.length() && p.charAt(pi) == '*')
                    ;
                return isMatch(s, p, si, pi);
            }
            return false;
        }

        if (pi < p.length() - 1 && p.charAt(pi + 1) == '*') {
            if ((s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '.')
                    && isMatch(s, p, si + 1, pi))
                return true;
            while (++pi < p.length() && p.charAt(pi) == '*')
                ;
            return isMatch(s, p, si, pi);
        } else if (s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '.')
            return isMatch(s, p, si + 1, pi + 1);

        return false;
    }

    // good for interview
    public boolean isMatchR0(String s, String p, int si, int pi) {

        // if pattern is empty, match is decided by string (empty string return true otherwise false)
        if (p.length() == pi)
            return s.length() == si;

        if (s.length() == si) {
            if (pi < p.length() - 1 && p.charAt(pi + 1) == '*') {
                pi++;
                while (pi < p.length() && p.charAt(pi) == '*')
                    pi++;
                return isMatchR0(s, p, si, pi);
            }
            return false;
        }

        if (pi < p.length() - 1 && p.charAt(pi + 1) == '*') {
            if ((s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '.')
                    && isMatchR0(s, p, si + 1, pi)) // it can match more s[si]
                return true;
            pi++;
            while (pi < p.length() && p.charAt(pi) == '*')
                pi++;
            return isMatchR0(s, p, si, pi);
        } else {
            if (p.charAt(pi) == '.' || p.charAt(pi) == s.charAt(si))
                return isMatchR0(s, p, si + 1, pi + 1);
            return false;
        }
    }
    
    public boolean isMatchRWithPlus(String s, String p, int si, int pi) {

        // if pattern is empty, match is decided by string (empty string return true otherwise false)
        if (p.length() == pi)
            return s.length() == si;

        if (s.length() == si) {
            if (pi < p.length() - 1 && p.charAt(pi + 1) == '*') {
                pi++;
                while (pi < p.length() && p.charAt(pi) == '*')
                    pi++;
                return isMatchRWithPlus(s, p, si, pi);
            }
            return false;
        }

        if (pi < p.length() - 1 && p.charAt(pi + 1) == '+') {
        	if (s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '.') {
        		int i = si + 1;
        		while (i < s.length() && s.charAt(i) == s.charAt(si)) {
        			i++;
        		}
        		return isMatchRWithPlus(s, p, i, pi + 2);
        	}
        	else {
        		return false;
        	}
        }
        else if (pi < p.length() - 1 && p.charAt(pi + 1) == '*') {
            if ((s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '.')
                    && isMatchRWithPlus(s, p, si + 1, pi)) // it can match more s[si]
                return true;
            pi++;
            while (pi < p.length() && p.charAt(pi) == '*')
                pi++;
            return isMatchRWithPlus(s, p, si, pi);
        } else {
            if (p.charAt(pi) == '.' || p.charAt(pi) == s.charAt(si))
                return isMatchRWithPlus(s, p, si + 1, pi + 1);
            return false;
        }
    }

    public boolean isMatchR(String s, String p, int si, int pi) {
        if (p.length() == pi)
            return s.length() == si;

        if (pi < p.length() - 1 && p.charAt(pi + 1) == '*') {
            if ((p.charAt(pi) == s.charAt(si) || p.charAt(pi) == '.')
                    && si < s.length() && isMatchR(s, p, si + 1, pi))
                return true;
            pi++;
            while (pi < p.length() && p.charAt(pi) == '*')
                pi++;
            return isMatchR(s, p, si, pi);
        } else {
            if ((p.charAt(pi) == s.charAt(si) || p.charAt(pi) == '.')
                    && si < s.length()) {
                return isMatchR(s, p, si + 1, pi + 1);
            }
            return false;
        }
    }

    // did not work
    public boolean isMatchR1(String s, String p, int si, int pi) {
        if (p.length() == pi)
            return s.length() == si;

        if (pi == p.length() - 1 || p.charAt(pi + 1) != '*') {
            if ((p.charAt(pi) == s.charAt(si) || p.charAt(pi) == '.')
                    && si < s.length())
                return isMatchR(s, p, si + 1, pi + 1);
            return false;
        } else {
            while (p.charAt(pi) == s.charAt(si) || p.charAt(pi) == '.'
                    && si < s.length()) {
                if (isMatchR(s, p, si, pi + 2))
                    return true;
                si++;
            }
            return isMatchR(s, p, si, pi + 2);
        }
    }

    /**
     * Another 
     * http://codereview.stackexchange.com/questions/10776/better-implementation-of-a-simplified-regular-expression-engine
     */

    /**
     * 
     */
    public RegularExpression() {
        // TODO Auto-generated constructor stub
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        RegularExpression re = new RegularExpression();
        String[] s = { "aa" };
        String[] p = { "a+" };
        for (int i = 0; i < s.length; i++) {
            System.out.printf("'%s' '%s' is match: %b", s[i], p[i], re.isMatch(
                    s[i], p[i]));
        }
        Integer [] a = new Integer[1];
        List<Integer> l = Arrays.asList(a);
    }

}
